package com.lisp.algorithm.c1e415;

public class MaxSubArray {

/*
    f(start) = f(start+1)              ; f-includeStart(start) < f(start+1)
             = f(start+1) + a[start]   ; f-includeStart(start) >= f(start+1)
             
    for i : 0 -> length {
        if(i == length-1) {
            return (length-1, length, a[length-1]);
        } else {
            (start, endExclude, sum)_i+1 = f(i+1);
            (start, endExclude, sum)_includei = f-includeStart(i);
            if(sum_includei >= sum_i+1) {
                return (start, endExclude, sum)_includei;
            } else {
                return (start, endExclude, sum)_i+1;
            }
        }
    }
*/    
    
    public static void main(String[] args) {
        int a[] = {2, -1, 1, -2, 1, 2, -1, 2, -3, 2, 1, 1};
        SubArray maxSubArray = maxSubArray(a, 0);
        System.out.println(maxSubArray);
    }
    
    public static SubArray maxSubArray(int a[], int start) {
        if(start == a.length - 1) {
            return new SubArray(start, a.length, a[start]);
        } else {
            SubArray subArray_f_n_1 = maxSubArray(a, start + 1);
            SubArray subArray_includeStart = maxSubArrayIncludeStart(a, start);
            if(subArray_includeStart.sum >= subArray_f_n_1.sum) {
                return subArray_includeStart;
            } else {
                return subArray_f_n_1;
            }
        }
    }
    
    public static SubArray maxSubArrayIncludeStart(int a[], int start) {
        int maxSum = Integer.MIN_VALUE;
        int sum = 0;
        int end = start + 1;
        for(int i=start; i<a.length; i++) {
            sum = sum+a[i];
            if(sum > maxSum) {
                maxSum = sum;
                end = i+1; // for exclusive
            }
        }
        return new SubArray(start, end, maxSum);
    }
}
